#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        //dp[i]  弄成值为i最少需要几个硬币
        vector<int> dp(amount+1,-1);
        dp[0] = 0;
        sort(coins.begin(),coins.end());
        for(int i = 0;i<coins.size()&&(amount>=coins[i]);++i){
            dp[coins[i]] = 1;
        }
        
        for(double i =coins[0];i<=amount;++i){
            if(dp[i]==-1){
                int temp = INT16_MAX;
                int status = 0;
                for(int j = 0;j<coins.size()&&(i>=coins[j]);++j){
                    if(dp[i-coins[j]]!=-1){
                        temp = min(temp,dp[coins[j]]+dp[i-coins[j]]);
                        status = 1;
                    }
                }
                if(status)
                    dp[i] = temp;
            }
        }
        int result = dp[amount];
        return result;
    }
};

int main(){
    Solution S;
    vector<int> coins = {2};
    cout<<S.coinChange(coins,3)<<endl;
}